package experiment1.sort;


import util.Util;

import static util.Util.random;
import static util.Util.swap;

public class QuickSort extends Sort {
    public QuickSort(int[] arr) {
        super(arr);
    }


    int partition(int left, int right) {
        int i = left, j = right + 1;

        int temp = arr[i];

        while (true) {
            while (arr[++i] < temp && i < right) ;
            while (temp < arr[--j]) ;
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
        }

        arr[left] = arr[j];
        arr[j] = temp;
        return j;
    }


    @Override
    public void sort(int left, int right) {
        if (left < right) {
//            int base = partition(left, right);
            //随机化快排
            int base = randomPartition(left,right);
            sort(left, base - 1);
            sort(base + 1, right);
        }
    }

    private int randomPartition(int left, int right) {
        int mid = random.nextInt(right - left + 1) + left;
        Util.swap(arr,mid,left);
        return partition(left,right);
    }

}
